package com.desin.modle.datastruct.algo.DynamicAlgorithm.charMatch;

import static com.google.common.primitives.Ints.min;

public class Solution {
    public int minNum = Integer.MAX_VALUE;

    public void test(int i,int j,int edit,char[] str,char[] target){
        int strLength = str.length;
        int tarLength = target.length;

        if(i==strLength||j==tarLength){
            if(i<strLength){
                edit = edit+strLength-i;
            }

            if(j<tarLength){
                edit = edit + tarLength-j;
            }

            if(edit<minNum){
                minNum = edit;
            }
            return;
        }

        if(str[i]==target[j]){
            test(i+1,j+1,edit,str,target);
        }else{
            test(i+1,j,edit+1,str,target);
            test(i,j+1,edit+1,str,target);
            test(i+1,j+1,edit+1,str,target);
        }
    }

    public int test1(char[] str,char[] target){
        int row = str.length;
        int column = target.length;

        int[][] states = new int[row][column];

        for(int i=0;i<row;i++){
            if(str[0]==target[i]){
                states[0][i] = i;
            }else if(i!=0){
                states[0][i] = states[0][i-1] +1;
            }else{
                states[0][i] = 1;
            }
        }

        for(int i=0;i<column;i++){
            if(str[i]==target[0]){
                states[i][0] = i;
            }else if(i!=0){
                states[i][0] = states[i-1][0] +1;
            }else{
                states[i][0] = 1;
            }
        }

        for(int i=1;i<row;i++){
            for(int j=1;j<column;j++){
                if(str[i]==target[j]){
                    states[i][j] = min(states[i-1][j]+1,states[i][j-1]+1,states[i-1][j-1]);
                }else{
                    states[i][j] = min(states[i-1][j]+1,states[i][j-1]+1,states[i-1][j-1]+1);
                }
            }
        }
        return states[row-1][column-1];
    }
}
